class Solution {
    private int m;
    private int n;
    private int[] disjointSet;
    private int[] dx = new int[]{0, 1, 0, -1};
    private int[] dy = new int[]{1, 0, -1, 0};
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        int count = m * n + 1;
        disjointSet = new int[count];
        for (int i = 0; i < count; i++) {
            disjointSet[i] = i;
        }
        int outer = count - 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') continue;
                int idx = n * i + j;
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) unionSet(idx, outer);
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || board[nx][ny] == 'X') continue;
                    unionSet(idx, n * nx + ny);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') continue;
                if (find(n * i + j) != find(outer)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
    private int find(int x) {
        if (disjointSet[x] == x) return x;
        return disjointSet[x] = find(disjointSet[x]);
    }
    private void unionSet(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            disjointSet[y] = x;
        }
    }
}
